import math
import numpy as np
import cupy as cp
import cProfile, pstats, io
np.seterr(invalid='ignore')
# 缓存构造算法
def count_digits(number):
    number_str = str(number)
    return len(number_str)
def cacheget(data):
    kcache = {}
    newdata = np.sort(data)
    q = 1
    while True:
         qnum = np.sum((data * q) % 1 == 0)
         if qnum == len(data):
             break
         else:
             q=q*10
    gcdtmp=q*newdata
    gcdtmp=gcdtmp.astype(int)
    kcache['k'] = np.gcd.reduce(gcdtmp)
    kcache['num'] = int((newdata[-1]-newdata[0])*(kcache['k']))+1
    kcache['min'] = newdata[0] *kcache['k']
    kcache['sort'] = newdata
    kcache['cp']=cp.array(newdata)
    kcache['cache'] = np.zeros((kcache['num'],1))
    #print(kcache['k'],kcache['min'],kcache['num'])
    tmpindex=kcache['k'] * newdata - kcache['min']
    tmpindex.astype(int)
    for i in range(len(newdata)):
        #print(tmp)
        kcache['cache'][tmpindex[i]] = newdata[i]
    numdata = [np.count_nonzero(data == val) for val in kcache['cache']]
    kcache['sum']=np.cumsum(kcache['cache'])
    kcache['num']=np.cumsum(numdata)
    #print(numdata)
    return kcache
def kmeanget(data):
    #print(data)
    arr=np.array(data)
    # 复制数组并向开头和结尾添加0
    arr_copy = np.copy(data)
    arr=np.insert(arr,0,0)
    arr_copy=np.append(arr_copy,0)
    #print(arr,arr_copy)
    arr=(arr+arr_copy)/2
    return arr[1:-1]
# 缓存索引获取算法
def get(kcache,i,name,indextmp):
    #print(func(tmp),len(kcache[name]))
    try:
        res=kcache[name][tmp]
    except:
        res=kcache[name][len(kcache[name])-1]
    return res
def getdiv(a,b):
     if b==0:
         return 0
     else:
         return a/b
def to(kcache, k, kmean,knum):
    #print(kcache['sum'],kcache['num'])
    indextmp = kmean * kcache['k'] - kcache['min']
    floortmp=np.floor(indextmp).astype(int)
    ceiltmp=np.ceil(indextmp).astype(int)
    #print(k)
    k[0] = getdiv(get(kcache,  0, 'sum',floortmp),get(kcache, 0, 'num',floortmp))
    for i in range(1, knum-2):
        k[i] = getdiv(get(kcache, i,  'sum',floortmp) - get(kcache, i-1,  'sum',ceiltmp),get(kcache,  i, 'num',floortmp) - get(kcache, i-1,  'num',ceiltmp))
    k[-1] = getdiv(kcache['sum'][-1] - get(kcache, knum-2,  'sum',ceiltmp),kcache['num'][-1]  - get(kcache,  knum-2,  'num',ceiltmp))
    kmean = kmeanget(k)
    return kmean, k
def seeget(k,kcache):
    sse=0
    ki=0
    kmean=kmeanget(k)
    kinum=[]
    for i in range(len(kmean)):
        while True:
            try:
                if kcache['sort'][ki] > kmean[i]:
                    kinum.append(ki)
                    break
                else:
                    ki = ki + 1
            except:
                break
    kinum=cp.array(kinum)
    #print(kinum,k,kcache['cp'])
    try:
        sse+=cp.sum(cp.power(kcache['cp'][0:kinum[0]]-k[0],2))
    except IndexError:
        pass
    for i in range(1,len(kinum)):
        try:
            sse += cp.sum(cp.power(kcache['cp'][kinum[i-1]:kinum[i]] - k[i], 2))
        except IndexError:
            pass
    try:
        sse+=cp.sum(cp.power(k[-1]-kcache['cp'][kinum[-1]:], 2))
    except IndexError:
        pass
    return float(sse)
class One:
     def __init__(self, knum, data):
        # 将数据转换为一维数组
        self.data = np.array(data).flatten()
        # 随机选择knum个数据点作为初始聚类中心
        self.k = np.sort(np.random.choice(self.data, knum, replace=False))
        self.sse = 0
        self.kcache=cacheget(self.data)
        self.kmean=kmeanget(self.k)
     def fit(self):
        (self.kmean,self.k)=to(self.kcache,self.k,self.kmean,len(self.k))
     def getsse(self):
         return seeget(self.k,self.kcache)
if __name__ == "__main__":
        import dataset
        import time
        import pandas
        data = list(pandas.read_excel('dataset.xlsx', header=None)[2])
        #b=time.perf_counter_ns()
        a=One(4,data)
        #print(a.k)
        #print(time.perf_counter_ns()-b)
        #b=time.perf_counter_ns()
        a.fit()
        #print(a.k)
        a.fit()
        #print(a.k)
        #print(time.perf_counter_ns()-b)
        a.getsse()